package com.lry.basic.algorithm.common;

class Solution {


    public static void main(String[] args) {
        System.out.println(integerReplacement(2147483647));
    }

    public static int integerReplacement(int n) {
        return integerReplacement2(n);
    }
    public static int integerReplacement2(long n) {
        if(n==1){
            return 0;
        }
        if((n&1)==0){
            return 1 + integerReplacement2(n/2);
        }else{
            return 1 + Math.min(integerReplacement2(n+1),integerReplacement2(n-1));
        }
    }

}